package 牛客.链表;

import 剑指offer.ListNode;

public class BM14链表的奇偶重排 {
    public ListNode oddEvenList (ListNode head) {
        // write code here
        //注意是节点的编号而非节点的数值
        if (head==null || head.next==null || head.next.next==null) {
            return head;
        }

        ListNode oddHead=null;//奇数位
        ListNode oddTail=null;
        ListNode evenHead=null;//偶数位
        ListNode evenTail=null;

        ListNode cur=head;
        int count=0;
        while (cur!=null) {
            if (count%2!=0) {
                if (oddHead==null) {
                    oddHead=cur;
                    oddTail=cur;
                }else {
                    oddTail.next=cur;
                    oddTail=cur;
                }
            }else  {
                if (evenHead==null) {
                    evenHead=cur;
                    evenTail=cur;
                }else {
                    evenTail.next=cur;
                    evenTail=cur;
                }
            }
            cur=cur.next;
            count++;
        }


        evenTail.next=oddHead;
        oddTail.next=null;
        return evenHead;

    }
}
